use std::cell::RefCell;
use std::rc::{Rc, Weak};

use crate::gen_title;

pub fn ch4_10_1() {
    gen_title("ch4_10_1", 18);

    #[derive(Debug)]
    enum List {
        Cons(i32, RefCell<Rc<List>>),
        Nil,
    }

    impl List {
        fn tail(&self) -> Option<&RefCell<Rc<List>>> {
            match self {
                List::Cons(_, item) => Some(item),
                List::Nil => None,
            }
        }
    }

    let a = Rc::new(List::Cons(5, RefCell::new(Rc::new(List::Nil))));

    println!("a的初始化rc计数 = {}", Rc::strong_count(&a));
    println!("a的指向节点 = {:?}", a.tail());

    let b = Rc::new(List::Cons(10, RefCell::new(Rc::clone(&a))));

    println!("在b创建后, a的计数 = {}", Rc::strong_count(&a));
    println!("b的初始化 rc 计数 = {}", Rc::strong_count(&b));
    println!("b指向的节点 = {:?}", b.tail());

    if let Some(link) = a.tail() {
        *link.borrow_mut() = Rc::clone(&b);
    }

    println!("在a的tail指向b后, b的计数 = {}", Rc::strong_count(&b));
    println!("在a的tail指向b后, a的计数 = {}", Rc::strong_count(&a));

    // println!("a指向的节点 = {:?}", a.tail());
}

pub fn ch4_10_2() {
    gen_title("ch4_10_2", 18);

    let five = Rc::new(5);

    let weak_five = Rc::downgrade(&five);

    let strong_five: Option<Rc<_>> = weak_five.upgrade();
    println!("strong_five = {}", strong_five.as_ref().unwrap());
    assert_eq!(*strong_five.unwrap(), 5);

    drop(five);

    let strong_five: Option<Rc<_>> = weak_five.upgrade();
    println!("strong_five = {:?}", strong_five);
    assert_eq!(strong_five, None);
}

pub fn ch4_10_3() {
    gen_title("ch4_10_3", 18);

    struct Gadget {
        id: i32,
        owner: Rc<Owner>,
    }

    struct Owner {
        name: String,
        gadgets: RefCell<Vec<Weak<Gadget>>>,
    }

    let gadget_owner: Rc<Owner> = Rc::new(Owner {
        name: "Gadget Man".to_string(),
        gadgets: RefCell::new(Vec::new()),
    });

    let gadget1 = Rc::new(Gadget {
        id: 1,
        owner: gadget_owner.clone(),
    });
    let gadget2 = Rc::new(Gadget {
        id: 2,
        owner: gadget_owner.clone(),
    });

    gadget_owner
        .gadgets
        .borrow_mut()
        .push(Rc::downgrade(&gadget1));
    gadget_owner
        .gadgets
        .borrow_mut()
        .push(Rc::downgrade(&gadget2));

    for gadget_opt in gadget_owner.gadgets.borrow().iter() {
        let gadget = gadget_opt.upgrade().unwrap();
        println!("Gadget {} owned by {}", gadget.id, gadget.owner.name);
    }
}

pub fn ch4_10_4() {
    gen_title("ch4_10_4", 18);

    #[derive(Debug)]
    struct Node {
        value: i32,
        parent: RefCell<Weak<Node>>,
        children: RefCell<Vec<Rc<Node>>>,
    }

    let leaf = Rc::new(Node {
        value: 3,
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(vec![]),
    });

    println!(
        "leaf strong = {}, weak = {}",
        Rc::strong_count(&leaf),
        Rc::weak_count(&leaf)
    );

    {
        let branch = Rc::new(Node {
            value: 5,
            parent: RefCell::new(Weak::new()),
            children: RefCell::new(vec![Rc::clone(&leaf)]),
        });

        *leaf.parent.borrow_mut() = Rc::downgrade(&branch);

        println!(
            "branch strong = {}, weak = {}",
            Rc::strong_count(&branch),
            Rc::weak_count(&branch)
        );

        println!(
            "leaf strong = {}, weak = {}",
            Rc::strong_count(&leaf),
            Rc::weak_count(&leaf)
        );
    }

    println!("leaf parent = {:?}", leaf.parent.borrow().upgrade());
    println!(
        "leaf strong = {}, weak = {}",
        Rc::strong_count(&leaf),
        Rc::weak_count(&leaf)
    )
}

pub fn ch4_10_5() {
    gen_title("ch4_10_5", 18);

    pub struct Tree {
        count: usize,
        root: *mut Node,
    }

    #[derive(Debug)]
    struct Node {
        data: i32,
        left: *mut Node,
        right: *mut Node,
        parent: *mut Node,
    }

    impl Tree {
        pub fn new() -> Self {
            Self {
                count: 0,
                root: std::ptr::null_mut(),
            }
        }

        pub fn node_count(&self) -> usize {
            assert!(self.count != 0 || self.root.is_null());
            self.count
        }

        pub fn insert(&mut self, data: i32) -> bool {
            if self.root.is_null() {
                self.root = Node::new(data);
            } else {
                if !Self::insert_node(self.root, data) {
                    return false;
                }
            }

            self.count += 1;
            true
        }

        pub fn find(&self, data: i32) -> bool {
            !Self::find_node(self.root, data).is_null()
        }

        pub fn display(&self) -> String {
            Self::display_node(self.root, 0)
        }

        pub fn inorder(&self) -> Vec<i32> {
            let mut v = vec![];
            if !self.root.is_null() {
                let mut node = Self::leftmost_child(self.root);
                loop {
                    if node.is_null() {
                        break;
                    }
                    unsafe {
                        v.push((*node).data);
                    }
                    node = Self::successor_of_node(node);
                }
            }
            v
        }

        pub fn remove(&mut self, data: i32) -> bool {
            let node = Self::find_node(self.root, data);
            if node.is_null() {
                false
            } else {
                self.remove_node(node);
                self.count -= 1;
                true
            }
        }

        pub fn successor(&self, data: i32) -> Option<i32> {
            unsafe {
                let node = Self::find_node(self.root, data);
                if !node.is_null() {
                    let nodesucc = Self::successor_of_node(node);
                    if !nodesucc.is_null() {
                        return Some((*nodesucc).data);
                    }
                }
                None
            }
        }

        pub fn remove_node(&mut self, node: *mut Node) {
            unsafe {
                let lchild = (*node).left;
                let rchild = (*node).right;
                if lchild.is_null() && rchild.is_null() {
                    self.replace_node(node, std::ptr::null_mut());
                } else if !lchild.is_null() && !rchild.is_null() {
                    let succ = Self::successor_of_node(node);
                    assert!(!succ.is_null());
                    (*node).data = (*succ).data;
                    self.remove_node(succ);
                } else if !lchild.is_null() {
                    self.replace_node(node, lchild);
                } else if !rchild.is_null() {
                    self.replace_node(node, rchild);
                } else {
                    panic!("unreachable")
                }
            }
        }

        pub fn replace_node(&mut self, node: *mut Node, r: *mut Node) {
            unsafe {
                let parent = (*node).parent;
                if parent.is_null() {
                    self.root = r;
                    if !r.is_null() {
                        (*r).parent = std::ptr::null_mut();
                    }
                } else {
                    if !r.is_null() {
                        (*r).parent = parent;
                    }
                    if (*parent).left == node {
                        (*parent).left = r
                    } else if (*parent).right == node {
                        (*parent).right = r
                    }
                }
                Box::from_raw(node);
            }
        }

        fn insert_node(node: *mut Node, data: i32) -> bool {
            unsafe {
                if (*node).data == data {
                    false
                } else if data < (*node).data {
                    if (*node).left.is_null() {
                        (*node).left = Node::new_with_parent(data, node);
                        true
                    } else {
                        Self::insert_node((*node).left, data)
                    }
                } else {
                    if (*node).right.is_null() {
                        (*node).right = Node::new_with_parent(data, node);
                        true
                    } else {
                        Self::insert_node((*node).right, data)
                    }
                }
            }
        }

        fn find_node(fromnode: *mut Node, data: i32) -> *mut Node {
            unsafe {
                if fromnode.is_null() || (*fromnode).data == data {
                    fromnode
                } else if data < (*fromnode).data {
                    Self::find_node((*fromnode).left, data)
                } else {
                    Self::find_node((*fromnode).right, data)
                }
            }
        }

        fn display_node(node: *const Node, indent: usize) -> String {
            let indent_str = " ".repeat(indent);
            if node.is_null() {
                indent_str + ".\n"
            } else {
                unsafe {
                    let mut s = format!("{}{}\n", indent_str, (*node).data);
                    s.push_str(&Self::display_node((*node).left, indent + 2));
                    s.push_str(&Self::display_node((*node).right, indent + 2));
                    s
                }
            }
        }

        fn leftmost_child(node: *mut Node) -> *mut Node {
            unsafe {
                if (*node).left.is_null() {
                    node
                } else {
                    Self::leftmost_child((*node).left)
                }
            }
        }

        fn successor_of_node(node: *mut Node) -> *mut Node {
            unsafe {
                if !(*node).right.is_null() {
                    Self::leftmost_child((*node).right)
                } else {
                    Self::parent_with_left(node)
                }
            }
        }

        fn parent_with_left(node: *mut Node) -> *mut Node {
            unsafe {
                let parent = (*node).parent;
                if !parent.is_null() {
                    if std::ptr::eq((*parent).left, node) {
                        return parent;
                    }
                    return Self::parent_with_left(parent);
                }

                std::ptr::null_mut()
            }
        }
    }

    impl Drop for Tree {
        fn drop(&mut self) {
            while !self.root.is_null() {
                self.remove_node(self.root);
            }
        }
    }

    impl Node {
        fn new(data: i32) -> *mut Self {
            Box::into_raw(Box::new(Self {
                data,
                left: std::ptr::null_mut(),
                right: std::ptr::null_mut(),
                parent: std::ptr::null_mut(),
            }))
        }

        fn new_with_parent(data: i32, parent: *mut Node) -> *mut Self {
            Box::into_raw(Box::new(Self {
                data,
                left: std::ptr::null_mut(),
                right: std::ptr::null_mut(),
                parent,
            }))
        }
    }

    let mut tree = Tree::new();
    tree.insert(1);
    tree.insert(2);
    tree.insert(3);

    println!("{}", tree.display());
    println!("{}", tree.find(2));
}
